/**
 * 不同路径 II
 * @description 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 *
 * @param {number} row 行
 * @param {number} col 列
 * @see https://leetcode-cn.com/problems/unique-paths-ii/
 */
function uniquePaths2(grid: number[][]) {
  const row = grid.length
  const col = grid[0].length
  /**
   * 初始化网格默认值
   */
  const dp: number[][] = Array.from({length: row}, () => Array(col).fill(0))

  for (let i = 0; i < row && grid[i][0] === 0; i++) dp[i][0] = 1
  for (let j = 0; j < col && grid[0][j] === 0; j++) dp[0][j] = 1

  for (let i = 1; i < row; i++) {
    for (let j = 1; j < col; j++) {
      if (grid[i][j] === 1) continue
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
    }
  }

  return dp[row-1][col-1]
}

const obstacleGrid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
]

const totalPaths = uniquePaths2(obstacleGrid)

console.log(totalPaths)
